\input{euler.tex}
\usepackage[pdftex]{graphicx}

\begin{document}

\problem[247]{Squares Under a Hyperbola}

Consider the region constrained by $x \ge 1$ and $0 \le y \le 1/x$.

Let $S_1$ be the largest square that can fit under the curve. Let $S_2$ be the largest square that fits in the remaining area, and so on. Below is an illustration of a few of such squares ($S_n$) labeled by $n$.

\begin{center}
\includegraphics[width=\linewidth]{p247_1.png}
\end{center}

Let the \emph{index} of $S_n$ be the pair (\emph{left}, \emph{below}) indicating the number of squares to the left of $S_n$ and the number of squares below $S_n$. For example, $S_2$ has one square to its left and none below, so the index of $S_2$ is $(1, 0)$.

It can be seen that the index of $S_{32}$ is $(1,1)$ as is the index of $S_{50}$. In fact, 50 is the largest $n$ for which the index of $S_n$ is $(1,1)$.

What is the largest $n$ for which the index of $S_n$ is $(3,3)$?

\solution

Since the squares are numbered by decreasing size, the square $S_n$ with index $(3,3)$ having the largest $n$ is the smallest square of all squares with index $(3,3)$. Therefore, we can generate all squares in decreasing size and calculate their indices, until all squares with index $(3,3)$ are generated. This is possible because each time a square is generated, either its \emph{left} index or \emph{below} index is incremented, so the number of squares with index within $(3,3)$ is finite.

To generate the squares in order, we first need to find an expression for the size of the largest square that fits into the unoccupied area. Looking at the graph, it's clear that the unoccupied areas are split into triangle-like \emph{segments}. Each segment is enclosed by the hyperbola $xy = 1$ and constrained by $x \ge x_0$ and $y \ge y_0$, where $x_0$ is the right-edge of the square on the left and $y_0$ is the top-edge of the square below.

For example, in the graph above, the first segment (counting from left) is enclosed by the vertical line $x = 1$ and $S_{66}$, the second segment by $S_{66}$ and $S_{12}$, the third by $S_{12}$ and $S_{32}$, the fourth by $S_{32}$ and $S_{75}$, and so on.

We start with the hyperbola itself, which can be viewed as a segment constrained by $x \ge 1$ and $y \ge 0$. Each time we generate a new square, we split one of the existing segments into two. Suppose we have generated $n$ squares, and thus have split the hyperbola into $n+1$ segments. To figure out where the next largest square should fit in, we can compute the largest square that could fit in each of the segments. We then pick the largest candidate as the next square.

Let $(x,y)$ be the coordinates of the upper-right corner of the largest square that fits under the hyperbola constrained by $x \ge x_0$ and $y \ge y_0$. Then we have
\[
x - x_0 = y - y_0 .
\]
Substituting in $y = 1/x$ and solving the equation, we get
\[
x = \frac{(x_0-y_0)+\sqrt{(x_0-y_0)^2+4}}{2} .
\]
Hence the size of the largest square (defined by its side length, $l$) is 
\[
l = \frac{\sqrt{(x_0-y_0)^2+4} - (x_0+y_0)}{2}.
\]

In the implementation, we store the segments in a priority queue, where the priority is defined as the side length of the largest square that fits in the segment. Each time a new square is needed, the segment with the highest priority is popped from the queue. It is then split into two sub-segments, and the sub-segments are inserted back into the queue according to their priority.

Along with each segment, we store the subscript of the two squares that mark the end points of the segment, so that when we add a new square under this segment we know what are the adjacent squares and hence can compute its (\emph{left}, \emph{below}) index.

To find the smallest square with index $(3,3)$, we use a counter to keep track of the number of segments whose fitting square has an index less than or equal to $(3,3)$ in both coordinates. If all the remaining segments would generate a square with larger index, we terminate the generation and the last square generated is the requested square.

Finally, we note that an alternative, two phase algorithm can compute the answer more quickly. The first phase finds the side length, $l_0$, of the smallest square with index $(3,3)$. This is fast because we can ignore all squares whose index (either \emph{left} or \emph{below}) is greater than 3. The second phase counts the number of squares whose side length is larger than $l_0$. This does not need a priority queue, and hence is faster than the above algorithm by a factor of $\ln n$. However, since the above algorithm is more ``interesting'', we will keep it as is.

\complexity

The algorithm is output-sensitive. Let $n$ be the subscript of the square found. Since we enumerate each square in order, the complexity is linear in $n$.

Time complexity: $\BigO(n)$.

Space complexity: $\BigO(n)$.

\answer

782252

\end{document} 